package leetCodeTest;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author liangzai
 * @Description:
 */
public class Training {
    //分割回文串 2
    List<List<String>> ans = new ArrayList<>();
    List<String> path = new ArrayList<>();
    int n;

    boolean isPalindrome(String s, int l, int r) {
        if (l > r)
            return false;
        while (l < r) {
            if (s.charAt(l++) != s.charAt(r--))
                return false;
        }
        return true;
    }

    private void dfs(String s, int i) {
        if (i == n) {
            ans.add(new ArrayList<>(path));
            return;
        }

        for (int j = i; j < n; ++j) {
            if (isPalindrome(s, i, j)) {
                path.add(s.substring(i, j + 1));
                dfs(s, j + 1);
                path.remove(path.size() - 1);
            }
        }
    }

    public int minCut(String s) {
        this.n = s.length();
        dfs(s, 0);
        int res = Integer.MAX_VALUE;
        for (List<String> cur : ans) {
            res = Math.min(res, cur.size() - 1);
        }
        return res;
    }
}
